#include<math.h>
#include <mpi.h>
#include <unistd.h>
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<string.h>
#include<time.h>
#include<ctype.h>
#include<sys/time.h>
#include <map>

using namespace std;

/* Tamanho máximo de uma palavra -> 5 letras + '\0' */
#define TAM_PALAVRA 6

/* Estrutura para armazenar as palavras */
map<string, bool> palavras;


/* Quebra as palavras de forma igualitaria e as insere na estrutura de palavras */
void insert(string palavra_grande){
  int i, tamanhoPalavra = palavra_grande.size(); 
  int qte_pedacos = ceil(((float)tamanhoPalavra) / (TAM_PALAVRA - 1)); 
  int size = ceil(((float)tamanhoPalavra) / qte_pedacos);
  string palavra;
  for(i = 0; i < tamanhoPalavra; i+=size){
     palavra = palavra_grande.substr(i, size);
     palavras[palavra] = true;
   }
}

/* Função que carrega o vetor de palavras do arquivo, salvando as palavras no vetor de palavras. Ao final ela retorna a quantidade de palavras da estrutura */
int carregaPalavras(FILE *fp){
  int i, tamanhoPalavra, qteNaoLetras;
  char buffer[50];
  string palavra;
  
  while (fscanf( fp, "%[^ ,\n\r]s", buffer) != EOF){
    tamanhoPalavra = strlen(buffer);
    
    /* Apenas considera palavras entre 2 e 20 letras */
    if(tamanhoPalavra > 1 && tamanhoPalavra < 20){
      
      /* Remove caracteres que não são letras e passa a palavra lida para minúsculo */
      qteNaoLetras = 0;
      for (i = 0; i < tamanhoPalavra; i++){
	if(!isalpha(buffer[i])){
	  qteNaoLetras++;
	  continue;
	}
	buffer[i-qteNaoLetras] = tolower(buffer[i]);
      }
      buffer[i-qteNaoLetras] = '\0';
      if(tamanhoPalavra - qteNaoLetras <= 1) continue;

      /* Insere a palavra (ou fragmentos dela) no vetor */
      palavra = buffer;
      insert(palavra);
    }
    /* Pula o caracter inválido */
    fgetc(fp); 
  } 
  return palavras.size();
}

/* Função que gera a palavra */
void gera_palavra(char* palavra){
  int i, tamanho;
  
  /* Sorteia um número para ser o tamanho da palavra a ser gerada (de 2 a 5 letras) */
  tamanho = (rand()%(TAM_PALAVRA-2)) + 2;
    
  /* Gera cada letra da palavra individualmente */
  for(i = 0; i < tamanho; i++){
    palavra[i] = (rand()%26) + 'a';  
  }
  /* Termina a palavra, colocando '\0' no final */
  palavra[i] = '\0';
}

/* Calcula o percentual de palavras encontradas */
float calculaPercentual(int achadas, int total){
  return (((float) achadas) / ((float) total));
}


int main(int argc, char *argv[]){
  int numPalavras, numAchadas = 0, i = 0;
  float faixa_percentual = 0.1;
  
  /* Iterador do map */
  map<string, bool>::iterator it;
  string palavra;
  
  /* Variáveis do MPI */
  int rank = 0, stop = 0, nro_processos = 1;
  MPI_Request solicitacao_envio;
  MPI_Status status;
  char buffer[TAM_PALAVRA];
  int flag = 0;
  
  /* Variáveis para registrar o tempo de início e término de execução */
  double start, end;
  
  /* Inicializa o MPI */
  if(MPI_Init(&argc, &argv) != MPI_SUCCESS){
    printf("Erro na inicialização da execução paralela com o MPI");
    return -1;	
  }
  
  /* Funções para pegar o número de threads e o rank do processo */
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  MPI_Comm_size(MPI_COMM_WORLD, &nro_processos);
  
  /* A implementação requer no mínimo 2 hosts */
  if (nro_processos < 2) {
    if (rank == 0) {
      printf("A implementacao requer no minimo 2 processos\n");
    }
    MPI_Finalize();
    return -1;
  }
  
  /* ==================================================================================================*/
  /* Inicializa e carrega a lista de palavras, registrando o tempo disso */
  FILE *fp;
  fp = fopen("palavras.txt", "r");
  if(fp < 0){
    printf("Não foi possivel abrir o arquivo de palavras\n");
    return -1;
  }
  start = MPI_Wtime();
  numPalavras = carregaPalavras(fp);
  end = MPI_Wtime();
  
  if(rank == 0){
    printf("=====================================\n");
    printf("Tempo carregando as palavras e removendo as repetidas = %f segundos\n", end-start);
    printf("Quantidade de palavras lidas = %d\n", numPalavras);
  }
  /* ==================================================================================================*/
  
  /* ==================================================================================================*/
  /* Agora começa a gerar as palavras */
  /* Registra tempo de início */
  start = MPI_Wtime();
  
  /* Semeia a palavra */
  srand(time(NULL)+rank);
  
  /* Como o envio da palavra ao MESTRE eh nao bloqueante, inicializa uma variavel de controle de envio de mensagens */
  solicitacao_envio = NULL;
  
  /* Primeiro nó (MESTRE)só receberá as palavras e contabilizará */
  if(rank == 0){
      do{    
	/*Verifico se algum dos outros processo enviou uma palavra para esse processo*/
	for(i = 1; i < nro_processos; i++){
	    /*Verifica se existe alguma mensagem disponivel, se existir o flag é setado para 1*/
	    MPI_Iprobe(i, rank, MPI_COMM_WORLD, &flag ,&status);
	    /*Se houver mensagem disponivel*/
	    if(flag){
	      /*Recebo o palavra*/
	      MPI_Recv(buffer, TAM_PALAVRA, MPI_CHAR, i, rank, MPI_COMM_WORLD, &status);

	      /*Retiro a palavra da lista de palavras se ela estiver la ainda*/
	      palavra = buffer;
	      it = palavras.find(palavra);
	      if (it != palavras.end()){
		palavras.erase(it);
		numAchadas++;      
		
		/* Verifica se passou de uma faixa percentual (10%, 20%, ...) */
		if(calculaPercentual(numAchadas, numPalavras) > faixa_percentual){
		  end = MPI_Wtime();
		  printf("Foram encontradas %d porcento das palavras em %.2f segundos\n", (int)(100.0 * faixa_percentual), end-start);
		  faixa_percentual += 0.1;
		}
	      }	
	    }
	}
      } while(numAchadas < numPalavras && stop == 0);
      
      /* Gerou todas as palavras. Registra tempo de fim */
      end = MPI_Wtime();
      
      /* Exibe os resultado */
      printf("-------------------------------------\n");
      printf("Tempo de execucao na geracao de palavras = %f segundos\n", end-start);
      printf("Quantidade de palavras encontradas = %d porcento\n", (int)(100.0 * calculaPercentual(numAchadas, numPalavras)));
      printf("=====================================\n");
      
      /* Manda os outros pararem */
      stop = 1; for(i = 1; i < nro_processos; i++) { MPI_Send(&stop, 1, MPI_INT, i, i, MPI_COMM_WORLD); } 
  }
  
  /* Outros nós (ESCRAVOS) gerarão as palavras e as enviarao ao Principal*/
  else{
    /* Loop de geracao de palavras */
    do{
      /*Gera uma palavra aleatoria*/
      gera_palavra(buffer);
      palavra = buffer;
      it = palavras.find(palavra);
      
      /*Se achar uma palavra que esta no dicionario*/
      if (it != palavras.end()){
	palavras.erase(it);
	numAchadas++;
	
	/* Envia para o nó de controle (MESTRE) */
	/*Se existir alguma solicitacao anterior de envio verifica se ja foi concluida*/
	if(solicitacao_envio != NULL){
	  status.MPI_SOURCE = -1;
	  status.MPI_TAG = -1;
	  /*Pego os status da solicitacao*/
	  MPI_Request_get_status( solicitacao_envio, &flag, &status);
	  /*Se nao tiver sido concluida fica esperando ser*/
	  while(!flag) MPI_Request_get_status( solicitacao_envio, &flag, &status);
	}
	/*Se a solicitacao anterior tiver sido terminada ou for a primeira ja envia*/
	if(flag || solicitacao_envio == NULL){
	  /*Envia a palavra do modo nao bloqueante... portanto ele n espera os dados serem transferidos para uma regiao de memoria
	  * onde o processo que vai receber ira pegar*/
	  MPI_Isend(buffer, TAM_PALAVRA, MPI_CHAR, 0, 0, MPI_COMM_WORLD, &solicitacao_envio);
	}
      }
      
      /* Verifica se recebeu aviso para parar */
	MPI_Iprobe(0, rank, MPI_COMM_WORLD, &flag ,&status);
	if(flag) {
	  MPI_Recv(&stop, 1, MPI_INT, 0, rank, MPI_COMM_WORLD, &status);
	  break;
	}
	
    } while(numAchadas < numPalavras && stop == 0);
  }
  /* ==================================================================================================*/    
  
  MPI_Barrier(MPI_COMM_WORLD);
  MPI_Finalize();
  
  return 0;  
}
